package seqlist.array.leetcode;

import java.util.Arrays;

/**
 * @author yuisama
 * @date 2023/03/09 19:23
 * 面试题17.04 缺失的数字
 **/
public class Num_17_04_MissingNumber {
    // 1.排序法
//    public int missingNumber(int[] nums) {
//        // 将nums数组排序
//        Arrays.sort(nums);
//        for (int i = 0; i < nums.length; i++) {
//            if (i != nums[i]) {
//                // 找到反例~
//                return i;
//            }
//        }
//        // 在循环中没找到反例，则缺失的数字就是长度n
//        return nums.length;
//    }
    // 2.哈希法
//    public int missingNumber(int[] nums) {
//        boolean[] hash = new boolean[nums.length + 1];
//        // 遍历原数组，将出现的值在对应的布尔数组下标置为true
//        for (int i = 0; i < nums.length; i++) {
//            hash[nums[i]] = true;
//        }
//        // 不存在的元素就是布尔数组中值为false的那个下标~
//        for (int i = 0; i < hash.length; i++) {
//            if (!hash[i]) {
//                // 说明此时i就是缺失的元素值
//                return i;
//            }
//        }
//        return -1;
//    }
    // 3.异或法
    public int missingNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res ^= i;
            res ^= nums[i];
        }
        res ^= nums.length;
        return res;
    }
}